|
In modular arithmetic, a branch of number theory, a number ''g'' is a primitive root modulo ''n'' if every number coprime to ''n'' is congruent to a power of ''g'' modulo ''n''. That is, for every integer ''a'' coprime to ''n'', there is an integer ''k'' such that ''g''''k'' ≡ ''a'' (mod ''n''). Such ''k'' is called the index or discrete logarithm of ''a'' to the base ''g'' modulo ''n''. In other words, ''g'' is a generator of the multiplicative group of integers modulo n. Gauss defined primitive roots in Article 57 of the Disquisitiones Arithmeticae (1801), where he credited Euler with coining the term. In Article 56 he stated that Lambert and Euler knew of them, but he was the first to rigorously demonstrate that primitive roots exist for a prime n. In fact, the ''Disquisitiones'' contains two proofs: the one in Article 54 is a nonconstructive existence proof, while the other in Article 55 is constructive. ==Elementary example== The number 3 is a primitive root modulo 7〔http://www.brynmawr.edu/math/people/stromquist/numbers/primitive.html〕 because :: Here we see that the period of 3''k'' modulo 7 is 6. The remainders in the period, which are 3, 2, 6, 4, 5, 1, form a rearrangement of all nonzero remainders modulo 7, implying that 3 is indeed a primitive root modulo 7. Curiously, permutations created in this way (and their circular shifts) have been shown to be Costas arrays. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「primitive root modulo n」の詳細全文を読む スポンサード リンク
|